package redbook;

import java.util.Arrays;
import java.util.Scanner;

/**
 * @author blh
 * @date 2024年06月28日 10:58
 */

public class Main3 {

    static int min = Integer.MAX_VALUE;


    public static void main(String[] args) {
        int[] a = new int[]{1, 2, 2, 2, 4};
        System.out.println(method(a));
    }

    static int method(int[] a) {
        int n = a.length;
        int sum = Arrays.stream(a).sum();
        int bagSize = sum / 2;
        // 在bagSize中最多装多少
        int[] dp = new int[bagSize + 1];

        // 先物品后背包
        for (int i = 0; i < a.length; i++) {
            for (int j = a[i]; j <= bagSize; j++) {
                dp[j] = Math.max(dp[j], dp[j - a[i]] + a[i]);
            }
        }

        return (sum - 2 * dp[bagSize]);

    }
}
